package com.ljy.my_study.leetcode.单词搜索;

/**
 * @author lijunying
 * @date 2021/9/22 15:41
 */
public class TestMain {

//    给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
//
//    单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
//
//             
//
//    示例 1：
//
//
//    输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
//    输出：true
//    示例 2：
//
//
//    输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
//    输出：true
//    示例 3：
//
//
//    输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
//    输出：false
//             
//
//    提示：
//
//    m == board.length
//            n = board[i].length
//1 <= m, n <= 6
//            1 <= word.length <= 15
//    board 和 word 仅由大小写英文字母组成
// 
//
//    进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/word-search
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    int[][] directions={{0,1},{1,0},{0,-1},{-1,0}};

    public boolean exist(char[][] board, String word) {
        int m=board.length;
        int n=board[0].length;
        boolean[][] visited=new boolean[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(dfs(board,i,j,word,0,visited)){
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board,int x,int y,String word,int index,boolean[][] visited){
        int m=board.length;
        int n=board[0].length;
        if(index>=word.length()){
            return false;
        }
        if(board[x][y]!=word.charAt(index)||visited[x][y]){
            return false;
        }
        if(index==word.length()-1){
            return true;
        }
        visited[x][y]=true;
        for(int i=0;i<directions.length;i++){
            int newX=x+directions[i][0];
            int newY=y+directions[i][1];
            if(newX<0||newX>=m||newY<0||newY>=n){
                continue;
            }
            boolean flag=dfs(board,newX,newY,word,index+1,visited);
            if(flag){
                return true;
            }
        }
        visited[x][y]=false;
        return false;
    }
}
